Cryptography systems are commonly used for providing secret communication of a text message or a cryptographic "key," or for authenticating identity of a sender via a digital signature. Once encoded, information is generally stored in a computer file (on a disk, for example) or transmitted to a desired recipient. So-called "public key cryptography" uses two asymmetric "keys," or large numbers, consisting of a public key and private key pair. If the public key is used to encode information according to a known algorithm, then the private key is usually needed by the recipient to decode that information, and vice-versa. Public key cryptography relies upon complex mathematical functions by which the public and private keys are related, such that it is extremely difficult to derive the private key from the public key, even with today's high speed processing computers.
One type of public key cryptography system is based upon elliptic curve representations and related mathematics and processing. As an end product of such processing, at least one coded block of information is created and represented as a data point having both X and Y coordinates, with each coordinate being a number between zero and 2.sup.N -1; if a large quantity of information is to be enciphered, there may be many such points, each point represented by at least 2N bits of information. For typical present day elliptic curve cryptography systems, N is typically on the order of one hundred and sixty, and future applications may use a much greater value for N.
In these cryptographic systems, a finite field is also chosen EQU F.sub.2.sub..sup.N ,
where N denotes the number of binary bits used by a computer to represent an element of the finite field. An irreducible generator polynomial or order N is then selected which defines the arithmetic operations in the field. The coefficients of an equation defining an elliptic curve are then selected, and a point P (having X and Y coordinates) on the elliptic curve. Once these terms are chosen, a "point addition" operation is defined, and from it a "point and multiplication" operation is thereby defined, EQU kP=P+P+P+ . . . +P,
i.e., P is added to itself P-1 times. With these terms, a private key consisting of one number, such as the number k, and a public key consisting of the product of the point P and the private key (the product being constrained by the finite field and the elliptic curve chosen) may be selected and used for public key cryptographic applications.
Cryptography generally does not address compact storage or transmission of data, which is the subject of "data compression." Data which is "compressed" occupies relatively less storage space and requires fewer transmission resources (i.e., time, bandwidth, storage, etc.) than uncompressed data. Without compression, transmission of relatively more information can lead to greater consumption of resources and frequency of errors. Modern day cryptography systems typically do not rely upon data compression, and they therefore leave some room for improvement.
Accordingly, a need exists for an elliptic curve processing system that compresses and decompresses coded data to a greater extent than known systems. Such a system should have application to cryptography systems which rely upon or process elliptic curve representations, enabling more efficient storage and transmission of encoded data. Still further, such a system should have the capability of compressing X and Y elliptic curve data coordinates, each having N bits, to a single representation having at most N bits in the aggregate. The present invention solves this need and provides further, related advantages.